public class demo1 {
    class Solution {
        boolean [][]flag;
        public boolean exist(char[][] board, String word) {
            int m=board.length;
            int n=board[0].length;
            flag=new boolean[m][n];
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(board[i][j]==word.charAt(0)){
                        flag[i][j]=true;
                        if(dfs(board,i,j,word,1))return true;
                        flag[i][j]=false;
                    }
                }
            }
            return false;
        }
        int []dx={0,0,1,-1};
        int []dy={1,-1,0,0};
        public boolean dfs(char[][] board,int i,int j,String word,int pos){
            if(pos==word.length()){
                return true;
            }
            for(int a=0;a<4;a++){
                int x=i+dx[a];
                int y=j+dy[a];
                if(x>=0&&x<board.length&&y>=0&&y<board[0].length&&!flag[x][y]&&board[x][y]==word.charAt(pos)){
                    flag[x][y]=true;
                    //找到一个true就一直返回true
                    if(dfs(board,x,y,word,pos+1))return true;
                    flag[x][y]=false;
                }
            }
            return false;
        }
    }
}
